def caching(func):
	from collections import defaultdict
	cache=defaultdict(int)
	def cached(*args):
		if not cache[args]:
			cache[args]=func(*args)
		return cache[args]
	return cached

def count_tree(lst):
	def get_right(i):
		if li[i]<1:
			return li[i]-1
		sigma=0
		while(sigma+1):
			i+=1
			sigma+=li[i]
		return i+1
	
	@caching
	def green(i,c):
		if i<0:return 0
		right=get_right(i)
		left=-1 if right<-1 else i+1
		if c:
			return 1+green(left,0)+green(right,0)
		return max(green(left,0)+green(right,1),green(left,1)+green(right,0))

	li=[0]+[x-1 for x in lst]
	return green(0,0)
	
from random import randrange as rr
# rr=lambda x:0
def build_tree(N):
	if N==0:return []
	if N==1:return [0]
	first=rr(N)
	second=N-first-1	
	this=[bool(first)+bool(second)]
	return this+build_tree(first)+build_tree(second)

from time import clock
tree=build_tree(5000)
print ''.join(map(lambda x:str(x),tree))
t=clock()
print count_tree(tree),'\n',clock()-t

